
/*! 
	\file		map.h
*	\brief		Provides a custom STL-like map template.
*/

#pragma once

#ifndef VLDBUILD
#error \
"This header should only be included by Visual Leak Detector when building it from source. \
Applications should never include this header."
#endif

#include "tree.h" // Provides access to the Tree template class.

/*!
	\class		Pair
	\brief		This is a lightweight STL-like pair template, for use with the lightweight
				Map class template.
	\remarks	while this is a STL-like class, it is not a full STL-compliant
				implementation of the STL pair utility class. It provides just the bare
				minimum functionality required by the Visual Leak Detector Map template
				class below.
*/
template <typename Tf, typename Ts>
class Pair {
public:
	// Constructor
	Pair ()
	{
		first = Tf();
		second = Ts();
	}

	// Constructor with initializers.
	Pair (const Tf &f, const Ts &s)
	{
		first = f;
		second = s;
	}

	/*!	
		\brief		
			Compares this Pair with another Pair to determine
			if this Pair is less than the other Pair. The Pair with the smallest
			"first" value is the lesser Pair.
		\param[in]  other
			The other pair to compare against.
		\return		
			Returns true if this Pair is less than the other Pair. Otherwise
			returns false.
	*/
	BOOL operator < (const Pair &other) const
	{
		return (first < other.first);
	}

	// Public data.
	Tf first;  //!< The first value of the pair.
	Ts second; //!< The second value of the pair.
};

/*!
	\class		Map
	\brief		This is a lightweidht STL-like map template. It makes use of the Tree class
				template to enable fast insert, find, and erase operations.
	\remarks	while this is a STL-like class, it is not a full STL-compliant
				implementation of the STL map container. It contains just the bare minimum
				functionality required by Visual Leak Detector. Because of its "lightweight"
				nature, this map class has a noticeable performance advantage over some
				other standard STL map implementations.
*/
template <typename Tk, typename Tv>
class Map {
public:
	class Iterator {
	public:
		// Constructor
		Iterator ()
		{
			// Plainly constructed iterators don't reference anything.
			m_node = NULL;
			m_tree = NULL;
		}

		/*!	
			\brief		
				Inequality operator for Map Iterators. Two Map
				Iterators are considered equal if and only if they both reference
				the same key/value pair in the same Map.
			\param[in]  other
				The other Map Iterator to compare against.
			\return		
				Returns true if the specified Map Iterator is not equal to this
				Map Iterator; otherwise, returns false.
		*/
		BOOL operator != (const Iterator &other) const
		{
			return ((m_tree != other.m_tree) || (m_node != other.m_node));
		}
		
		/*!	
			\brief		
				Dereference operator for Map Iterators.
			\remarks  
				The reference returned by this function is "const", so the
				value referenced by the Iterator may not be modified through the
				Iterator. This is a departure from STL iterator behavior.

				Also, dereferencing an Iterator which does not reference a valid
				value in the Map is undefined and will almost certainly cause a
				crash.
			\return		
				Returns a const reference to the key/value pair in the Map
				referenced by the Iterator.
		*/
		const Pair<Tk, Tv>& operator * () const
		{
			return m_node->key;
		}

		/*!	
			\brief		
				Prefix increment operator for Map Iterators. Causes the
				Iterator to reference the in-oder successor of the key/value pair
				currently referenced by the Iterator. If the Iterator is currently
				referencing the largest key/value pair in the Map, then the
				resulting Iterator will reference the Map's end (the NULL pair).
			\remarks  
				Incrementing an Iterator which does not reference a valid
				key/value pair in the Map is undefined and will almost certainly
				cause a crash.
			\return		
				Returns the Iterator after it has been incremented.
		*/
		Iterator& operator ++ (int)
		{
			m_node = m_tree->next(m_node);
			return *this;
		}

		/*!	
			\brief		
				Postfix increment operator for Map Iterators. Causes
				the Iterator to reference the in-order successor of the key/value
				pair currently referenced by the Iterator. If the Iterator is
				currently referencing the largest key/value pair in the Map, then
				the resulting Iterator will reference the Map's end (the NULL
				pair).
			\remarks  
				Incrementing an Iterator which does not reference a valid
				key/value pair in the Map is undefined and will almost certainly
				cause a crash.
			\return		
				Returns the Iterator before it has been incremented.
		*/
		Iterator operator ++ ()
		{
			typename Tree<Pair<Tk, Tv> >::node_t *cur = m_node;

			m_node = m_tree->next(m_node);
			return Iterator(m_tree, cur);
		}

		/*!	
			\brief		
				Subtraction operator for Map Iterators. Causes the
				the Iterator to reference a key/value pair that is an in-order
				predecessor of the currently referenced key/value pair.
			\param[in]  num
				Number indicating the number of preceding key/value
				pairs to decrement the iterator.
			\return		
				Returns an Iterator referencing the key/value pair that precedes
				the original Iterator by "num" pairs.
		*/
		Iterator operator - (SIZE_T num) const
		{
			typename Tree<Pair<Tk, Tv> >::node_t *cur = m_node;

			for (SIZE_T count = 0; count < num; count++)  {
				cur = m_tree->prev(cur);
				if (cur == NULL) {
					return Iterator(m_tree, NULL);
				}
			}
			return Iterator(m_tree, cur);
		}
		
		/*!	
			\brief		
				Equality operator for Map Iterators. Map Iterators are
				considered equal if and only if they both reference the same
				key/value pair in the same Map.
			\param[in]  other
				The other Map Iterator to compare against.
			\return		
				Returns true if the specified Map Iterator is equal to this Map
				Iterator; otherwise returns false.
		*/
		BOOL operator == (const Iterator &other) const
		{
			return ((m_tree == other.m_tree) && (m_node == other.m_node));
		}

	private:
		/*! Private constructor. Only the Map class itself may use this
		   constructor. It is used for constructing Iterators which reference
		   specific nodes in the internal tree's structure.
		*/
		Iterator (const Tree<Pair<Tk, Tv> > *tree, typename Tree<Pair<Tk, Tv> >::node_t *node)
		{
			m_node = node;
			m_tree = tree;
		}

		typename Tree<Pair<Tk, Tv> >::node_t *m_node; //!< Pointer to the node referenced by the Map Iterator.
		const Tree<Pair<Tk, Tv> >            *m_tree; //!< Pointer to the tree containing the referenced node.

		friend class Map<Tk, Tv>;	//!< The Map class is a friend of Map Iterators.
	};
	
	/*!	
		\brief		
			Obtains an Iterator referencing the beginning of the Map (i.e.
			the lowest key/value pair currently stored in the Map).
		\return		
			Returns an Iterator referencing the first key/value pair in the Map.
			If no key/value pairs are currenly stored in the map, returns the
			"NULL" Iterator.
	*/
	Iterator begin () const
	{
		return Iterator(&m_tree, m_tree.begin());
	}

	/*!	
		\brief		
			Obtains an Iterator referencing the end of the Map. The end of
			the map does not reference an actual key/value pair. Instead it
			represents a "null" key/value pair which signifies the end (i.e. just
			beyond largest key/value pair currently stored in the Map). Also
			known as the "NULL" Iterator.
		\return		
			Returns the "NULL" Iterator, signifying the end of the Map.
	*/
	Iterator end () const
	{
		return Iterator(&m_tree, NULL);
	}
	
	/*!	
		\brief		
			Erases a key/value pair from the map.
		\param[in]  it
			Iterator referencing the key/value pair to be erased from the map.
		\return		
			None.
	*/
	VOID erase (Iterator& it)
	{
		m_tree.erase(it.m_node);
	}
	
	/*!	
		\brief		
			Erases a key/value pair from the map.
		\param[in]  key
			The key corresponding to the key/value pair to be erased from the map.
		\return		
			None.
	*/
	VOID erase (const Tk &key)
	{
		m_tree.erase(Pair<Tk, Tv>(key, Tv()));
	}

	/*!	
		\brief		
			Finds a key/value pair in the map.
		\param[in]  key
			The key corresponding to the key/value pair to be found.
		\return		
			Returns an Iterator referencing the found key/value pair. If no
			key/value pair with the specified key could be found, then the "NULL"
			Iterator is returned.
	*/
	Iterator find (const Tk &key) const
	{
		return Iterator(&m_tree, m_tree.find(Pair<Tk, Tv>(key, Tv())));
	}

	/*!	
		\brief		
			Inserts a key/value pair into the map.
		\param[in]  key
			The key of the key/value pair to be inserted.
		\param[in]  data
			The value of the key/value pair to be inserted.
		\return		
			Returns an Iterator referencing the resulting key/value pair after
			if has been inserted into the map.
	*/
	Iterator insert (const Tk &key, const Tv &data)
	{
		return Iterator(&m_tree, m_tree.insert(Pair<Tk, Tv>(key, data)));
	}

	/*!	
		\brief		
			Sets the reserve size of the map. The reserve size is the
			number of key/value pairs for which space should be pre-allocated
			to avoid frequent heap hits when inserting new key/value pairs into
			the map.
		\param[in]  count
			The number of key/value pairs for which to reserve space in advance.
		\return		
			Returns the reserve size previously in use by the map.
	*/
	size_t reserve (size_t count)
	{
		return m_tree.reserve(count);
	}

private:
	// Private data
	Tree<Pair<Tk, Tv> > m_tree; //!< The key/value pairs are actually stored in a tree.
};
